package com.frank.leetcode.question_16_20;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Collections;

/**
 * https://leetcode-cn.com/problems/3sum-closest/description/
 * 16. 最接近的三数之和
 * 难度: 中等
 * <p>
 * <p>
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * <p>
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 * <p>
 * <p>
 * Created by zhy on 2018/8/14.
 */
public class ThreeSumClosest {
    private static Logger LOG = LoggerFactory.getLogger(ThreeSumClosest.class);

    @Test
    public void run() {
//        int[] nums = {0, 1, 1, 1};
//        int target = 100;

        int[] nums = {-3,-2,-5,3,-4};
        int target = -1;
//        int[] nums = {1, 2, 4, 8, 16, 32, 64, 128};
//        int target = 82;
        System.out.println(threeSumClosest(nums,target));
//        System.out.println(threeSumClosest_best(nums, target));
    }

    private int threeSumClosest(int[] nums, int target) {
        int near = Integer.MAX_VALUE;//差值
        int sum = 0;//最接近的和
        Arrays.sort(nums);//排序
        t0:
        for (int i = 0; i < nums.length - 2; i++) {
            t1:
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int s = nums[i] + nums[j] + nums[k];
                    int m = s - target;
                    int v = Math.abs(s - target);
                    LOG.info("i:{},j:{},k:{},s:{},m:{},v:{},sum:{},near:{}", i, j, k, s, m, v, sum, near);
                    if (v < near) {
                        near = v;
                        sum = s;
                        if (v == 0) break t0;
                    } else if (m > 0 && (i + 2 == k)) {
                        break t1;
                    }
                }
            }
        }

        System.out.println("最接近的和:" + sum + " target : " + target + "  差值: " + (Math.abs(target - sum)));
        return sum;
    }


    public int threeSumClosest_best(int[] nums, int target) {
        int minVal = Integer.MAX_VALUE;
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int diff = Math.abs(sum - target);
                LOG.info("i:{},j:{},k:{},s:{},m:{},v:{},sum:{},near:{}", i, j, k, sum, diff);
                if (sum == target) {
                    return sum;
                } else if (sum > target) {
                    k--;
                    if (diff < minVal) {
                        minVal = Math.min(diff, minVal);
                        result = sum;
                    }
                } else {
                    j++;
                    if (diff < minVal) {
                        minVal = Math.min(diff, minVal);
                        result = sum;
                    }
                }
            }
        }
        return result;
    }
}